package 纯数组;

import java.util.*;
import java.util.function.BiConsumer;

public class No713乘积小于K的子数组 {

    /**
     * 给定一个正整数数组 nums。
     * 找出该数组内乘积小于 k 的连续的子数组的个数。
     *
     * 示例 1:
     * 输入: nums = [10,5,2,6], k = 100
     * 输出: 8
     * 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
     * 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
     * 说明:
     * 0 < nums.length <= 50000
     * 0 < nums[i] < 1000
     * 0 <= k < 10^6
     */

    /**
     * 小于k的 连续子数组积
     * 都是正整数,要懂得变通,双指针。
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {

        int left=0;
        int right=0;
        int product=1;
        int result=0;

        while (right<nums.length){

            product*=nums[right];

            while (left<=right&&product>=k){
                //当前积不小于k
                product/=nums[left++];
            }

            result+=(right-left+1);

            right++;
        }

        return result;
    }

    public static void main(String[] args) {
        No713乘积小于K的子数组 n=new No713乘积小于K的子数组();
        int[] arr={3,1,25,361,6,31,245,12,531};
        int result = n.numSubarrayProductLessThanK(arr, 30);
        System.out.println(result);
    }

}
